/**
 * 141.环形链表
 * 142.环形链表II
 * 287.寻找重复数  -- 环形链表思想
 * 面试题02.07.链表相交
 * **/

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
public:
    //141.
    bool hasCycle(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
    // 142. 采坑：fast，slow都得从head开始
    ListNode *detectCycle(ListNode *head)
    {
        if (!head || !head->next) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        bool hasCycle = false;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return nullptr;
        }
        // 有环
        while (head != slow) {
            head = head->next;
            slow = slow->next;
        }
        return slow;
    }
    // 287. 寻找重复数
    // 长度为n+1的数组nums，只包含一个重复数字，找出那个重复数
    int findDuplicate(vector<int> &nums)
    {
        // 方法一：二分查找，每次先猜一个数，然后统计<=mid的个数
        // 每次都能筛掉半个区间  O(NlogN) + O(1)
#if 0
        int n = nums.size();
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid){
                    ++cnt;
                }
            }
            if (cnt <= mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
#endif
        // 方法二：环形链表思想 O(N) + O(1)
        // 而且是必有环的情况
        // idx->nums[idx] 把数组的值理解成next指针
        int slow = 0, fast = 0;
        while (1) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if (slow == fast) {
                break;
            }
        }
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
    // 面试题02.07.
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *curA = headA, *curB = headB;
        while (curA != curB) {
            curA = curA ? curA->next : headB;
            curB = curB ? curB->next : headA;
        }
        return curA;
    }
};

Solution solve = Solution();

int main()
{
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 5};
    cout << solve.findDuplicate(nums) << endl; // 5
    return 0;
}